#include<iostream>
#include<vector>
#include<queue>
#include<string>
using namespace std;

struct Node{
    int x;
    int y;
    Node(int x, int y):x(x),y(y){};
};
vector<vector<bool>> visited;
int numIslands(vector<vector<char>>& grid) {
    vector<vector<bool>> visited(grid.size(),vector<bool>(grid[0].size()));
    queue<Node*> q;
    int count = 0;
    for(int i=0;i<grid.size();i++)
    {
        for(int j=0;j<grid[i].size();j++)
        {
            //先遍历第一个元素，如果为1且未被访问过，则开始进行广度优先搜索
            if(grid[i][j]=='1'&&!visited[i][j])
            {
                count++;
                Node* root = new Node(i,j);
                q.push(root);
                visited[i][j] = true;
                while(q.size())
                {
                    int size = q.size();
                    //将队列中的元素的所有为1的邻接元素进队然后将对头元素出队
                    for(int k=0;k<size;k++)
                    {
                        Node* node = q.front();
                        int x = node->x;
                        int y = node->y;
                        int x1 = x-1;
                        int x2 = x+1;
                        int y1 = y-1;
                        int y2 = y+1;
                        if(x1>=0&&grid[x1][y]=='1'&&!visited[x1][y])
                        {
                            Node* child = new Node(x1,y);
                            q.push(child);
                            visited[x1][y] = true;
                        }
                        if(x2<grid.size()&&grid[x2][y]=='1'&&!visited[x2][y])
                        {
                            Node* child = new Node(x2,y);
                            q.push(child);
                            visited[x2][y] = true;
                        }
                        if(y1>=0&&grid[x][y1]=='1'&&!visited[x][y1])
                        {
                            Node* child = new Node(x,y1);
                            q.push(child);
                            visited[x][y1] = true;
                        }
                        if(y2<grid[0].size()&&grid[x][y2]=='1'&&!visited[x][y2])
                        {
                            Node* child = new Node(x,y2);
                            q.push(child);
                            visited[x][y2] = true;
                        }
                        q.pop();
                    }
                }

            }
        }
    }
    return count;        
}

int main()
{
    vector<vector<char>> grid(4);
    cout<<"enter the 2d array"<<endl;
    for(int i=0;i<grid.size();i++)
    {
        for(int j=0;j<5;j++)
        {
            char x;
            cin>>x;
            grid[i].push_back(x);
        }
    }
    cout<<"the 2d array is"<<endl;
    for(int i=0;i<grid.size();i++)
    {
        for(int j=0;j<5;j++)
        {
            cout<<grid[i][j]<<' ';
        }
        cout<<endl;
    }
    int number = numIslands(grid);
    cout<<"the number of islands is "<<number;
    return 0;
}